eps = 1e-6


def f(x):
    return x


'''
实数三分
'''


def TernarySearch():
    l, r = 1, int(1e18)
    while r - l > eps:
        mid = (l + r) / 2
        fl, fr = f(mid - eps), f(mid + eps)
        if fl < fr:
            l = mid
        else:
            r = mid


'''
整数三分
要求连续两数不等,不然会错
'''
def search(l, r):
    while r - l > 4:
        m1 = l + (r - l) // 3
        m2 = r - (r - l) // 3
        v1, v2 = f(m1), f(m2)
        if v1 < v2:
            r = m2
        #     求最大改成l = m1
        else:
            l = m1
        #     求最大改成 r = m2
    v, idx = f(l), l
    for i in range(l + 1, r + 1):
        vv = f(i)
        if vv > v:
            v = vv
            idx = i
    return (v, idx)
